/* Generates about 1 MB of random data that is then divided into
   16 chunks.  A separate subprocess sorts each chunk in
   sequence.  Then we merge the chunks and verify that the result
   is what it should be. */

#include <syscall.h>
#include "tests/arc4.h"
#include "tests/lib.h"
#include "tests/main.h"

/* This is the max file size for an older version of the Pintos
   file system that had 126 direct blocks each pointing to a
   single disk sector.  We could raise it now. */
#define CHUNK_SIZE (126 * 512)
#define CHUNK_CNT 16                       /* Number of chunks. */
#define DATA_SIZE (CHUNK_CNT * CHUNK_SIZE) /* Buffer size. */

unsigned char buf1[DATA_SIZE], buf2[DATA_SIZE];
size_t histogram[256];

/* Initialize buf1 with random data,
   then count the number of instances of each value within it. */
static void init(void)
{
    struct arc4 arc4;
    size_t i;

    msg("init");

    arc4_init(&arc4, "foobar", 6);
    arc4_crypt(&arc4, buf1, sizeof buf1);
    for (i = 0; i < sizeof buf1; i++)
        histogram[buf1[i]]++;
}

/* Sort each chunk of buf1 using a subprocess. */
static void sort_chunks(void)
{
    size_t i;

    create("buffer", CHUNK_SIZE);
    for (i = 0; i < CHUNK_CNT; i++)
    {
        pid_t child;
        int handle;

        msg("sort chunk %zu", i);

        /* Write this chunk to a file. */
        quiet = true;
        CHECK((handle = open("buffer")) > 1, "open \"buffer\"");
        write(handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
        close(handle);

        /* Sort with subprocess. */
        CHECK((child = exec("child-sort buffer")) != -1,
              "exec \"child-sort buffer\"");
        CHECK(wait(child) == 123, "wait for child-sort");

        /* Read chunk back from file. */
        CHECK((handle = open("buffer")) > 1, "open \"buffer\"");
        read(handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
        close(handle);

        quiet = false;
    }
}

/* Merge the sorted chunks in buf1 into a fully sorted buf2. */
static void merge(void)
{
    unsigned char *mp[CHUNK_CNT];
    size_t mp_left;
    unsigned char *op;
    size_t i;

    msg("merge");

    /* Initialize merge pointers. */
    mp_left = CHUNK_CNT;
    for (i = 0; i < CHUNK_CNT; i++)
        mp[i] = buf1 + CHUNK_SIZE * i;

    /* Merge. */
    op = buf2;
    while (mp_left > 0)
    {
        /* Find smallest value. */
        size_t min = 0;
        for (i = 1; i < mp_left; i++)
            if (*mp[i] < *mp[min])
                min = i;

        /* Append value to buf2. */
        *op++ = *mp[min];

        /* Advance merge pointer.
           Delete this chunk from the set if it's emptied. */
        if ((++mp[min] - buf1) % CHUNK_SIZE == 0)
            mp[min] = mp[--mp_left];
    }
}

static void verify(void)
{
    size_t buf_idx;
    size_t hist_idx;

    msg("verify");

    buf_idx = 0;
    for (hist_idx = 0; hist_idx < sizeof histogram / sizeof *histogram;
         hist_idx++)
    {
        while (histogram[hist_idx]-- > 0)
        {
            if (buf2[buf_idx] != hist_idx)
                fail("bad value %d in byte %zu", buf2[buf_idx], buf_idx);
            buf_idx++;
        }
    }

    msg("success, buf_idx=%'zu", buf_idx);
}

void test_main(void)
{
    init();
    sort_chunks();
    merge();
    verify();
}
